package everydayone.reversePair;

import java.util.ArrayList;

/**
 * @Date 2020/04/24
 * @author 王光浩
 * @Thinking 改进暴力法
 * 	         从后向前进行遍历，每次遍历之后，将以及遍历的数字加入到一个有序的集合中，这个集合是按照从大到小的顺序存储数据的
 * 		当我们遍历到下一个元素时，获取出当前集合的元素总个数，然后我们找出该元素在集合中的下标，将元素总个数-下标就是
 * 		所有比当前元素小的元素的个数。
 * @Analysis 时间复杂度O（n^2），空间复杂度O（n）
 */
public class MyMethodTwo {
	public int reversePairs(int[] nums) {
		if( nums==null || nums.length<=1 ) return 0;
		int ret = 0;
		ArrayList<Integer> help = new ArrayList<Integer>();
		help.add(nums[nums.length-1]);
		for(int i=nums.length-2 ; i>=0 ; i--) {
			//利用二分法找到 nums[i] 应当插入的位置
			int left = 0;
			int right = help.size()-1;
			int mid ;
			while( left<=right ) {
				mid = left+(right-left)/2;
				if( help.get(mid)>=nums[i] )
					left = mid+1;
				else
					right = mid-1;
			}
			if( left==help.size() ) help.add(nums[i]);
			else help.add(left, nums[i]);
			//计算需要插入位置之后的元素个数
			ret += help.size()-right-2;			
		}
		return ret;
	}
}
